#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class Solution
{
public:
    // f[n] = max{f[n-1] + a[n],a[n]}
    int maxSubArray(vector<int> &nums)
    {
        if (nums.size() == 0)
            return 0;
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int maxsum = dp[0];
        for (int i = 1; i < dp.size(); ++i)
        {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            maxsum = max(dp[i], maxsum);
        }
        return maxsum;
    }
};